The composition of panoramas from a collection of smaller individual images has recently become a popular application in digital image processing. With the introduction of low-cost, robotic tripod heads along with the improvement of image registration techniques, panoramas are becoming larger and more complex. In the past, these image collections were captured in one sweeping motion such that image overlaps were in only one dimension. Today's images are often collections of multiple rows and columns, and thus, overlap in two dimensions. Today's images further may be arranged in unstructured configurations. The fully composited panoramic image can range from a few megapixels to many gigapixels in size. As a result, more sophisticated panorama processing techniques continue to be developed to account for their more complex configurations and larger sizes.
A fundamental step in stitching several pictures to form a larger mosaic is the computation of boundary seams that minimize the visual artifacts due to the transition between images. Current seam computation algorithms use optimization methods that may be slow, sequential, memory intensive, and prone to finding suboptimal solutions related to local minima of the chosen energy function. Currently, the most used technique for global seam computation in a panorama is the Graph Cuts algorithm. For reference, see for example, R. Zabih et al., Fast Approximate Energy Minimization Via Graph Cuts, Int'l Conference Computer Vision 377-384 (1999); Y. Boykov & V. Kolmogorov, An Experimental Comparison of Min-cut/Max-Flow Algorithms for Energy Minimization in Vision, 26 IEEE Transactions on Pattern Analysis and Mach. Intelligence 9, 1124-1137 (2004); and V. Kolmogorov & R. Zabih, What Energy Functions can be Minimized Via Graph Cuts?, 26 IEEE Transactions on Pattern Analysis and Mach. Intelligence 2, 147-159 (2004). This is a popular and robust computer vision technique and has been adapted to compute the boundary between a collection of images. While this technique has been used with good success for a variety of panoramic or similar graphics applications, it can be problematic due to its high computational cost and memory requirements. Moreover, Graph Cuts applied to digital panoramas is a serial operation. Additionally, even when the various known techniques perform well, what they compute may not provide perceptually ideal or even good seams between the input images.